package tree;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;
/**
 * 二叉数的遍历
 * 					+
 * 				-		 E
 * 			*		D
 *  	/		C
 * 	 A		B
 * @author Ranter
 *
 */
public class TreeUtil {
	//中序遍历		左-根-右	（前中后：根的位置）
	public static void InOrder(TreeNode current){
		if(current != null) {
			InOrder(current.left);
			Visit(current);
			InOrder(current.right);
		}
	}
	//前序遍历		根-左-右
	public static void PreOrder(TreeNode current){
		if(current != null) {
			Visit(current);
			InOrder(current.left);
			InOrder(current.right);
		}
	}
	//后续遍历		左-右-根
	public static void PostOrder(TreeNode current){
		if(current != null) {
			InOrder(current.left);
			InOrder(current.right);
			Visit(current);
		}
	}
	//层序遍历		同一层节点从左往右依次遍历(使用队列层序遍历)
	public static void LevelOrder(TreeNode current){
		List<TreeNode> q = new ArrayList<TreeNode>();
		while(current != null) {
			Visit(current);
			if(current.left != null) {
				q.add(current.left);
			}
			if(current.right != null) {
				q.add(current.right);
			}
			if(q.isEmpty()) return ;
			current = q.remove(0);
		}
	}
	
	//*********辅助工具****************
	public static void Visit(TreeNode node) {
		System.out.print(node.val + " ");
	}
}

